/*
快速排序：指定一个key 用其作为分界点，左边均小于他 右边均大于他     时间：O(nlog2n)  空间复杂度为O(log2n) 因为递归/迭代均需要栈
 */
function quickSort(nums) {
    // 递归出口
    if (nums.length <= 1) return nums
    let mid = 0
    let left = []
    let right = []
    for (let i = 1; i < nums.length; i ++) {
        if (nums[i] < nums[mid]) {
            left.push(nums[i])
        }
        else {
            right.push(nums[i])
        }
    }
    // 返回的是左边的排序结果 + key值 + 右边的排序结果
    return [...quickSort(left), nums[mid], ...quickSort(right)]
}

console.log(quickSort([4, 2, 8, 9, 1, 7, 10, 3, 0]));
